Path-Fault-Tolerant Approximate Shortest-Path Trees

摘要

Let $G=(V,E)$ be an $n$-nodes non-negatively real-weighted undirected graph.In this paper we show how to enrich a {\em single-source shortest-path tree}(SPT) of $G$ with a \emph{sparse} set of \emph{auxiliary} edges selected from$E$, in order to create a structure which tolerates effectively a \emph{pathfailure} in the SPT. This consists of a simultaneous fault of a set $F$ of atmost $f$ adjacent edges along a shortest path emanating from the source, and itis recognized as one of the most frequent disruption in an SPT. We show that,for any integer parameter $k \geq 1$, it is possible to provide a very sparse(i.e., of size $O(kn\cdot f^{1+1/k})$) auxiliary structure that carefullyapproximates (i.e., within a stretch factor of $(2k-1)(2|F|+1)$) the trueshortest paths from the source during the lifetime of the failure. Moreover, weshow that our construction can be further refined to get a stretch factor of$3$ and a size of $O(n \log n)$ for the special case $f=2$, and that it can beconverted into a very efficient \emph{approximate-distance sensitivity oracle},that allows to quickly (even in optimal time, if $k=1$) reconstruct theshortest paths (w.r.t. our structure) from the source after a path failure,thus permitting to perform promptly the needed rerouting operations. Ourstructure compares favorably with previous known solutions, as we discuss inthe paper, and moreover it is also very effective in practice, as we assessthrough a large set of experiments.